package com.leetcode.LeetCode精选TOP面试题;

import com.leetcode.common.model.TreeNode;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author 覃国强
 * @date 2022-06-13 11:21
 */
public class 题库_0102_二叉树的层序遍历 {

  static
  class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
      List<List<Integer>> answers = new ArrayList<>();
      if (root == null) {
        return answers;
      }

      Deque<TreeNode> cur = new ArrayDeque<>();
      Deque<TreeNode> next = new ArrayDeque<>();
      cur.add(root);

      while (!cur.isEmpty()) {
        List<Integer> answer = new ArrayList<>();
        while (!cur.isEmpty()) {
          TreeNode node = cur.remove();
          answer.add(node.val);
          if (node.left != null) {
            next.add(node.left);
          }
          if (node.right != null) {
            next.add(node.right);
          }
        }
        answers.add(answer);
        Deque<TreeNode> temp = cur;
        cur = next;
        next = temp;
      }

      return answers;
    }
  }

}
